The present invention relates generally to decision-making logic devices in a computing system, and specifically to arbitration devices which arbitrate between clients within the system.
An arbiter is a computing device which is used to select one from a plurality of clients requesting access to a specific computing resource. The arbiter receives a plurality of requests from the clients, and chooses one of the requests to have access to the resource. The client whose request is chosen to have access is herein termed the arbitration-winning client. Arbiters known in the art implement a variety of different arbitration schemes, including priority schemes wherein different clients are assigned different fixed priorities.
For example, in one common type of arbitration system, incoming requests are logged in registers. Each client is assigned a register in the arbiter, so that a specific register holds pending requests for that client. Combinatorial logic is used to define the next request to be served at any time, using priority schemes as are known in the art. The logic acts as a bottleneck for the arbiter, and the size of the logic grows in proportion to the square of the number of clients.
Another type of arbitration system simply uses a first-in first-out (FIFO) memory device. Each new request is stored at the tail of the device, and the request at the head of the FIFO receives the service. This system is limited by the size of the FIFO, which depends on the number of requests, rather than the number of clients. Depending on the arbitration system, the number of requests can be orders of magnitude larger than the number of clients.
Other arbitration schemes include round-robin and time-sharing schemes. Hardware arbiters known in the art typically require combinatorial logic paths whose length, and thus the size of the logic, is directly proportional to the square of the number of clients utilizing the resource. As the size of the logic increases, the time for arbitration also increases. Depending on the application, arbiters in a computing system may receive requests from thousands of clients, necessitating arbiters having large logic sizes.
It is an object of some aspects of the present invention to provide an arbiter which utilizes reduced logic size and which is able to arbitrate efficiently between large numbers of clients.
It is a further object of some aspects of the present invention to provide an arbiter comprising logic circuitry whose size is substantially independent of the number of clients using the arbiter.
It is another object of some aspects of the present invention to provide an arbiter wherein the time taken to perform an arbitration is substantially independent of the number of clients using the arbiter.
It is yet a further object of some aspects of the present invention to provide an arbiter utilizing a memory whose size scales as substantially less than the square of the number of clients.
In preferred embodiments of the present invention, a hardware-based arbiter which arbitrates between a plurality of clients in a computing environment is implemented as a linked-list device. The plurality of clients are resident in a memory of the computing environment, and produce multiple requests for use of a specific resource of the environment. As the plurality of clients produce requests for the resource, the requests are directed to the arbiter. For each client requesting use of the resource, the arbiter updates a number-of-requests value and a next-client-to-use-the-resource pointer, hereinafter termed a next-client pointer, and enters these updated parameters into a table comprised in the arbiter. The next-client pointers link their respective clients in a uni-directional list. At times when the resource is available, the arbiter utilizes the list to arbitrate between the plurality of clients and so generate an arbitration-winning client, which client is given access by the arbiter to the resource.
The arbiter manages the table by arbiter-specific logic circuitry incorporated into the arbiter, the size of which logic is relatively small and is independent both of the number of clients and of the number of requests. The size of the arbiter is thus roughly equal to the size of the table generated by the arbiter. The size of the table is directly proportional to the number of clients requesting use of the resource, herein termed N, and to the size of the entries of the table. The size of the entries is of the order of log2(N), so that the total size of the arbiter is of the order of Nxc2x7log2(N). Thus the size of the arbiter, especially for large values of N, is significantly smaller than arbiters known in the art which use combinatorial logic. Furthermore, since the timing of arbitration performed by the arbiter is a function of the size of the logic circuitry, the timing is substantially independent of the number of clients and the number of requests from the clients. While linked lists have been used in software-based arbitration, the present invention is the first practical implementation of a linked-list structure in hardware. It thus provides a substantially faster and more economical solution to the problem of arbitration among large numbers of clients than has heretofore been known in the art.
In some preferred embodiments of the present invention, one or more input devices are added to the arbiter in order to separate requests which would otherwise arrive substantially simultaneously at the arbiter.
In some preferred embodiments of the present invention, requests from different clients may be assigned to more than one priority level. Additional sets of pointers, according to the number of priority levels, are incorporated in the arbiter. The additional sets of pointers enable the arbiter to arbitrate between the different priority requests.
There is therefore provided, according to a preferred embodiment of the present invention, an arbiter which arbitrates between a plurality of clients generating requests for access to a resource in a computing environment, including:
a memory, including for each of the plurality of clients:
a request register, which is adapted to record the respective client""s access requests; and
a next-client pointer, which is adapted to record an identification of another one of the clients making a subsequent request to access the resource, so as to form a linked list of the requests; and
logic circuitry which is adapted to decide, responsive to the linked list, which of the plurality of clients is given access to the resource.
Preferably, the memory includes at least one list-terminating pointer which indicates an end of the linked list.
Preferably, the at least one list-terminating pointer includes a tail pointer which indicates a last client in the linked list.
Preferably, the at least one list-terminating pointer includes a head pointer which indicates a first client in the linked list, and the logic circuitry is operative to decide, responsive to the head pointer, which of the plurality of clients is given access to the resource.
Preferably, the logic circuitry is operative to check whether a client requesting access to the resource has a pending access request, and to update a record of the number of pending access requests recorded in the respective register responsive to the check.
Preferably, the logic circuitry is operative to check whether the resource is available, and to allocate the resource responsive to the check.
Preferably, the arbiter includes at least one buffer wherein requests from a specific client are stored before being recorded in the respective request register.
Further preferably, the arbiter includes a first-in first-out memory wherein requests from the plurality of clients are stored before being transferred sequentially to the memory and the logic circuitry.
Preferably, the memory includes:
for at least some of the clients, a priority flag which is adapted to record a priority for access to the resource for the at least some clients; and
at least one list-terminating pointer for the priority, which indicates an end of the linked list for the at least some clients.
Preferably, the logic circuitry is adapted to decide, responsive to the linked list and the priority flag, which of the clients is given access to the resource.
Further preferably, the logic circuitry is of a size that is substantially independent of the number of clients served by the arbiter, and the circuitry is adapted to decide, responsive to the recorded requests, which of the plurality of clients is given access to the resource.
Preferably, a size of the memory scales as a product of the number of clients and a logarithm of the number of clients.
There is further provided, according to a preferred embodiment of the present invention, an arbiter serving a plurality of clients that generate requests for access to a resource in a computing environment, including:
a memory, including a respective register assigned to each of the plurality of clients, which register is adapted to record the respective client""s access requests; and
logic circuitry, of a size that is substantially independent of the number of clients served by the arbiter, which circuitry is adapted to decide, responsive to the recorded requests, which of the plurality of clients is given access to the resource.
Preferably, the size of the memory scales as a product of the number of clients and a logarithm of the number of clients.
There is further provided, according to a preferred embodiment of the present invention, a method for arbitrating between a plurality of clients generating requests for access to a resource in a computing environment, including:
for each of the plurality of clients, recording the client""s access requests in a respective, dedicated memory register;
recording for each of the clients, responsive to the requests, a next-client pointer to a subsequent one of the clients requesting the resource, so as to form a linked list of the clients; and
giving the clients access to the resource responsive to the linked list.
Preferably, recording the next-client pointer includes pointing to an end of the linked list with a list-terminating pointer.
Preferably, pointing to the end of the linked list includes pointing to a last client in the linked list with a tail pointer.
Further preferably, pointing to the end of the linked list includes pointing to a first client in the linked list with a head pointer, and giving the clients access to the resource includes giving the clients access to the resource responsive to the head pointer.
Preferably, recording the client""s access requests includes checking if a client requesting access to the resource has a pending request, and updating the memory register responsive to the check.
Preferably, giving the clients access includes checking whether the resource is available, and allocating the resource responsive to the check.
Preferably, recording the client""s access requests includes providing at least one buffer and storing the requests from the client in the buffer prior to recording the client""s access requests.
Preferably, giving the clients access includes assigning priorities to at least some of the clients, and forming a linked list of the prioritized clients.
Further preferably, giving the clients access to the resource includes deciding, responsive to the assigned priorities and the linked list, which of the clients is given access to the resource.
There is further provided, according to a preferred embodiment of the present invention, a method for arbitrating between a plurality of clients generating requests for access to a resource in a computing environment, including:
for each of the plurality of clients, recording the client""s access requests;
providing logic circuitry of a size that is substantially independent of the number of the plurality of clients; and
utilizing the logic circuitry to decide, responsive to the recorded requests, which of the plurality of clients is given access to the resource.
The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings, in which: